home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_400 / 420_02 / varray.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-02-27  |  16.8 KB  |  450 lines
  1. #ifndef VARRAY_H
  2. #define VARRAY_H
  3.  
  4. //      This is a template for a virtual array of type T.
  5.  
  6. #include <stdio.h>
  7. #include <dos.h>
  8.  
  9. #ifndef TRUE
  10. #define TRUE -1
  11. #endif
  12. #ifndef FALSE
  13. #define FALSE 0
  14. #endif
  15.  
  16. template <class T>
  17. class varray
  18.   {
  19.     private:
  20.       int          expanded_memory_allocated(void);
  21.                     // Allocated expanded memory.  If this can't be done,
  22.                     // an attempt will be made to use a disk instead.
  23.       unsigned int expanded_memory_handle;
  24.       int          free_expanded_memory;
  25.       int          free_disk_memory;
  26.                     // The temporary file used for virtual memory needs to be
  27.                     // freed.
  28.       void         free_memory(void);
  29.                     // Free real memory used for pages, etc.
  30.       int          free_real_memory;
  31.                     // Real memory needs to be freed.
  32.       int          map_expanded_memory(int physical_page,long logical_page);
  33.                     // Associate a physical page in the physical page frame
  34.                     // with a logical page of expanded memory.
  35.       int          memory_allocated(void);
  36.                     // Allocate real memory for pages, etc.
  37.       long         num_elements_in_array;
  38.                     // Number of elements in the array.
  39.       unsigned int num_elements_per_page;
  40.                     // Number of array elements in a page.
  41.       int          num_real_pages;
  42.                     // Number of pages kept in real memory.
  43.       char         *page_frame_ptr;
  44.                     // Pointer to expanded memory physical frame.
  45.       T            **real_page;
  46.                     // A page in real memory.
  47.       long         *starting_element_num;
  48.                     // Index of first array element in page in real memory.
  49.       FILE         *vm;
  50.                     // Temporary file used for virtual memory.
  51.       long         *vm_access;
  52.                     // "When" a page in real memory was last accessed.
  53.       long         vm_access_num;
  54.                     // Current "time".
  55.     public:
  56.       int allocated(void) {return (free_real_memory &&
  57.            (free_expanded_memory || free_disk_memory));}
  58.  
  59.           varray(T& initialized_element,long element_count,
  60.            int real_page_count=4,unsigned int page_size=32768);
  61. //      Construct a virtual array of type T.  The arguments are as follow:
  62. //
  63. //           initialized_element -- an initialized element of type T.
  64. //
  65. //           element_count -- the number of elements in the array.
  66. //   
  67. //           real_page_count -- the number of pages to be kept in memory.
  68. //      This should be at least as large as the maximum number of elements
  69. //      of the array referenced at once.  Small values result in too much
  70. //      paging; large values result in too much overhead searching for the
  71. //      page containing an element.
  72. //
  73. //           page_size -- the number of bytes in a page.  This must be at least
  74. //      sizeof(T).  This is used only when a disk is used for virtual memory.
  75. //      (When expanded memory is used, the page size is effectively 32K.)  32K 
  76. //      is probably optimal due to the overhead of searching for a page.
  77.  
  78.           ~varray(void);
  79. //      If expanded memory was used, free it.  If a temporary file was used,
  80. // close (and so delete) it.  If real memory was allocated, free it.
  81.  
  82.       T   *vm_ptr(long element_num);
  83. //      Return a pointer to an element of the array.  When T is a structure, it
  84. // is faster to use this pointer than to overload [] and search virtual memory
  85. // for each component of the structure.
  86.  
  87.       T&  operator[](long element_num) {return *vm_ptr(element_num);}
  88. //     Return an element of the array by overloading [].
  89.   };
  90.  
  91. template <class T>
  92. varray<T>::varray(T& initialized_element,long element_count,int real_page_count,
  93.  unsigned int page_size)
  94. //      Construct a virtual array of type T.  The arguments are as follow:
  95. //
  96. //           initialized_element -- an initialized element of type T.
  97. //
  98. //           element_count -- the number of elements in the array.
  99. //   
  100. //           real_page_count -- the number of pages to be kept in memory.
  101. //      This should be at least as large as the maximum number of elements
  102. //      of the array referenced at once.  Small values result in too much
  103. //      paging; large values result in too much overhead searching for the
  104. //      page containing an element.
  105. //
  106. //           page_size -- the number of bytes in a page.  This must be at least
  107. //      sizeof(T).  This is used only when a disk is used for virtual memory.
  108. //      (When expanded memory is used, the page size is effectively 32K.)  32K 
  109. //      is probably optimal due to the overhead of searching for a page.
  110.   {
  111.     unsigned int element_index;
  112.     long         element_num;
  113.  
  114.     free_real_memory=FALSE;
  115.     free_disk_memory=FALSE;
  116.     free_expanded_memory=FALSE;
  117.     num_real_pages=real_page_count;
  118.     num_elements_in_array=element_count;
  119.     if (sizeof(T) <= 32768)
  120.       {      
  121.         num_elements_per_page=32768/sizeof(T);
  122.         free_expanded_memory=expanded_memory_allocated();
  123.       }
  124.     if (free_expanded_memory)
  125.       if (memory_allocated()) // Allocate space for the active pages.
  126.         {
  127.           free_real_memory=TRUE;
  128.           long expanded_memory_page_num=0L;
  129.           int real_page_num=0;
  130.           vm_access_num=0;
  131.           int successful=TRUE;
  132.           for (element_num=(long) 0;
  133.            ((successful) && (element_num < num_elements_in_array));
  134.            element_num+=((long) num_elements_per_page))
  135.             {
  136.               if (real_page_num < real_page_count)
  137.               // Initialize real page.
  138.                 {
  139.                   vm_access_num++;
  140.                   for (element_index=(unsigned int) 0;
  141.                    element_index < num_elements_per_page;
  142.                    element_index++)
  143.                     real_page[real_page_num][element_index]
  144.                      =initialized_element;
  145.                   vm_access[real_page_num]=vm_access_num;
  146.                   starting_element_num[real_page_num]=element_num;
  147.                   real_page_num++;
  148.                 }
  149.               // Initialize virtual page.
  150.               if (successful=map_expanded_memory(0,expanded_memory_page_num++))
  151.                 {
  152.                   if (successful
  153.                    =map_expanded_memory(1,expanded_memory_page_num++))
  154.                     memcpy((void *) page_frame_ptr,(void *) &(real_page[0][0]),
  155.                      num_elements_per_page*sizeof(T));
  156.                 }
  157.             }
  158.           if (! successful)
  159.             cerr
  160.              << "Fatal error:  there is an unexpected problem with expanded "
  161.              << "memory." << '\n';
  162.         }
  163.       else
  164.         cerr << "Fatal error:  not enough real memory for virtual array." 
  165.          << '\n';
  166.     else
  167.       {
  168.         num_elements_per_page=page_size/sizeof(T);
  169.         if ((vm=tmpfile()) == NULL) // Get a file for the virtual memory.
  170.           cerr << "Fatal error:  cannot open virtual memory." << '\n';
  171.         else
  172.           if (memory_allocated()) // Allocate space for the active pages.
  173.             {
  174.               free_real_memory=TRUE;
  175.               free_disk_memory=TRUE;
  176.               int real_page_num=0;
  177.               vm_access_num=0;
  178.               int successful=TRUE;
  179.               for (element_num=(long) 0;
  180.                ((successful) && (element_num < num_elements_in_array));
  181.                element_num+=((long) num_elements_per_page))
  182.                 {
  183.                   if (real_page_num < real_page_count)
  184.                   // Initialize real page.
  185.                     {
  186.                       vm_access_num++;
  187.                       for (element_index=(unsigned int) 0;
  188.                        element_index < num_elements_per_page;
  189.                        element_index++)
  190.                         real_page[real_page_num][element_index]
  191.                          =initialized_element;
  192.                       vm_access[real_page_num]=vm_access_num;
  193.                       starting_element_num[real_page_num]=element_num;
  194.                       real_page_num++;
  195.                     }
  196.                   // Initialize virtual page.
  197.                   successful=(fwrite(&(real_page[0][0]),
  198.                    sizeof(T),num_elements_per_page,vm)
  199.                    == num_elements_per_page);
  200.                 }
  201.               if (! successful)
  202.                 cerr
  203.                  << "Fatal error:  not enough disk space for virtual array."
  204.                  << '\n';
  205.             }
  206.           else
  207.             cerr << "Fatal error:  not enough real memory for virtual array." 
  208.              << '\n';
  209.       }
  210.   }
  211.  
  212. template <class T>
  213. varray<T>::~varray()
  214. //      If expanded memory was used, free it.  If a temporary file was used,
  215. // close (and so delete) it.  If real memory was allocated, free it.
  216.   {
  217.     if (free_expanded_memory)
  218.       {
  219.         union REGS input_reg;
  220.         union REGS output_reg;
  221.  
  222.         input_reg.h.ah=0x45;
  223.         input_reg.x.dx=expanded_memory_handle;
  224.         int86(0x67,&input_reg,&output_reg);
  225.       }
  226.     if (free_disk_memory)
  227.       fclose(vm);
  228.     if (free_real_memory)
  229.       free_memory();
  230.   };
  231.  
  232. template <class T>
  233. int varray<T>::expanded_memory_allocated()
  234.   {
  235.     char              *EMM_device_name = "EMMXXXX0";
  236.     union REGS        input_reg;
  237.     union
  238.       {
  239.         unsigned long device_name_address;
  240.         char          *device_name_ptr;
  241.       };
  242.     union REGS        output_reg;
  243.     union
  244.       {
  245.         unsigned long pf_address;
  246.         char          *pf_ptr;
  247.       };
  248.     long              pages_needed;
  249.     int               result;
  250.     struct SREGS      segment_reg;
  251.  
  252.     typedef T *t_ptr;
  253.  
  254.     result=FALSE;
  255.     pages_needed=num_elements_in_array/long(num_elements_per_page);
  256.     if (pages_needed*long(num_elements_per_page) < num_elements_in_array)
  257.       pages_needed++;
  258.     pages_needed+=pages_needed; // VARRAY uses 32K byte pages; 
  259.                                 // expanded memory uses 16K byte pages.
  260.     if (pages_needed <= 0xffff)
  261.       {      
  262.         input_reg.h.ah=0x35;
  263.         input_reg.h.al=0x67;
  264.         intdosx(&input_reg,&output_reg,&segment_reg);
  265.         device_name_address=(((unsigned long) (segment_reg.es)) << 16) + 10L;
  266.         if (memcmp(EMM_device_name,device_name_ptr,8) == 0)
  267.           {
  268.             input_reg.h.ah=0x42;
  269.             int86(0x67,&input_reg,&output_reg);
  270.             if ((output_reg.h.ah == 0)
  271.             &&  (pages_needed <= long(output_reg.x.bx)))
  272.               {
  273.                 input_reg.h.ah=0x43;
  274.                 input_reg.x.bx=(unsigned int) pages_needed;
  275.                 int86(0x67,&input_reg,&output_reg);
  276.                 expanded_memory_handle=output_reg.x.dx;
  277.                 if (output_reg.h.ah == 0)
  278.                   {
  279.                     input_reg.h.ah=0x41;
  280.                     int86(0x67,&input_reg,&output_reg);
  281.                     if (result=(output_reg.h.ah == 0))
  282.                       {
  283.                         pf_address=(((unsigned long) (output_reg.x.bx)) << 16);
  284.                         page_frame_ptr=pf_ptr;
  285.                       }
  286.                   }
  287.               }
  288.           }
  289.       }
  290.     return result;
  291.   }
  292.  
  293. template <class T>
  294. int varray<T>::memory_allocated()
  295. //      Allocate real memory for pages, etc.
  296.     {
  297.       int result;
  298.       int real_page_num;
  299.  
  300.       typedef T *t_ptr;
  301.  
  302.       if (result=((vm_access=new long[num_real_pages]) != NULL))
  303.         {
  304.           if (result=((starting_element_num=new long[num_real_pages]) != NULL))
  305.             if (result=((real_page=new t_ptr[num_real_pages]) != NULL))
  306.               {
  307.                 for (real_page_num=0;
  308.                  ((result) && (real_page_num < num_real_pages));
  309.                  real_page_num++)
  310.                   result=((real_page[real_page_num]
  311.                    =new T[num_elements_per_page]) != NULL);
  312.                 if (! result)
  313.                   {
  314.                     --real_page_num;
  315.                     while (real_page_num > 0)
  316.                       delete[] real_page[--real_page_num];
  317.                     delete[] real_page;
  318.                   }
  319.               }
  320.             else
  321.               {
  322.                 delete[] starting_element_num;
  323.                 delete[] vm_access;
  324.               }
  325.           else
  326.             delete[] vm_access;
  327.         }
  328.       return(result);
  329.     };
  330.  
  331. template <class T>
  332. void varray<T>::free_memory()
  333. //      Free real memory used for pages, etc.
  334.     {
  335.       for (int real_page_num=0; real_page_num < num_real_pages; real_page_num++)
  336.         delete[] real_page[real_page_num];
  337.       delete[] real_page;
  338.       delete[] starting_element_num;
  339.       delete[] vm_access;
  340.       return;
  341.     };
  342.  
  343. template <class T>
  344. T *varray<T>::vm_ptr(
  345.   long element_num)
  346. //      Return a pointer to an element of the array.
  347.     {
  348.       long earliest_access;
  349.       long expanded_memory_page_num;
  350.       int  num_oldest_real_page;
  351.       int  page_found;
  352.       int  real_page_num;
  353.       T    *result;
  354.       long virtual_page_num;
  355.  
  356.       vm_access_num++;
  357.       page_found=FALSE;
  358.       num_oldest_real_page=0;
  359.       earliest_access=vm_access[0];
  360.       for (real_page_num=0;
  361.        ((! page_found) && (real_page_num < num_real_pages));
  362.        real_page_num++)
  363.         if ((element_num >= starting_element_num[real_page_num])
  364.         &&  (element_num < ((long) num_elements_per_page)
  365.          +(starting_element_num[real_page_num])))
  366.           page_found=TRUE;
  367.         else
  368.           {
  369.             if (vm_access[real_page_num] < earliest_access)
  370.               {
  371.                 earliest_access=vm_access[real_page_num];
  372.                 num_oldest_real_page=real_page_num;
  373.               }
  374.           }
  375.       if (page_found) // Page is already in real memory.
  376.         {
  377.           real_page_num--;
  378.           result=&(real_page[real_page_num]
  379.            [element_num-starting_element_num[real_page_num]]);
  380.           vm_access[real_page_num]=vm_access_num;
  381.         }
  382.       else // Swap oldest page in real memory for the one sought.
  383.         if (free_expanded_memory)
  384.           {
  385.             virtual_page_num=starting_element_num[num_oldest_real_page]
  386.              /((long) num_elements_per_page);
  387.             expanded_memory_page_num=virtual_page_num;
  388.             expanded_memory_page_num+=expanded_memory_page_num;
  389.             map_expanded_memory(0,expanded_memory_page_num++);
  390.             map_expanded_memory(1,expanded_memory_page_num);
  391.             memcpy((void *) page_frame_ptr,
  392.              (void *) &(real_page[num_oldest_real_page][0]),
  393.              num_elements_per_page*sizeof(T));
  394.             virtual_page_num=element_num/((long) num_elements_per_page);
  395.             expanded_memory_page_num=virtual_page_num;
  396.             expanded_memory_page_num+=expanded_memory_page_num;
  397.             map_expanded_memory(0,expanded_memory_page_num++);
  398.             map_expanded_memory(1,expanded_memory_page_num);
  399.             memcpy((void *) &(real_page[num_oldest_real_page][0]),
  400.              (void *) page_frame_ptr,
  401.              num_elements_per_page*sizeof(T));
  402.             starting_element_num[num_oldest_real_page]
  403.              =virtual_page_num*((long) num_elements_per_page);
  404.             result=&(real_page[num_oldest_real_page][
  405.              element_num-starting_element_num[num_oldest_real_page]]);
  406.             vm_access[num_oldest_real_page]=vm_access_num;
  407.           }
  408.         else
  409.           {
  410.             fseek(vm,
  411.              starting_element_num[num_oldest_real_page]*((long) sizeof(T)),
  412.              SEEK_SET);
  413.             fwrite(&(real_page[num_oldest_real_page][0]),sizeof(T),
  414.              num_elements_per_page,vm);
  415.             starting_element_num[num_oldest_real_page]
  416.              =element_num/((long) num_elements_per_page);
  417.             (starting_element_num[num_oldest_real_page])
  418.              *=((long) num_elements_per_page);
  419.             fseek(vm,
  420.              starting_element_num[num_oldest_real_page]*((long) sizeof(T)),
  421.              SEEK_SET);
  422.             fread(&(real_page[num_oldest_real_page][0]),sizeof(T),
  423.              num_elements_per_page,vm);
  424.             result=&(real_page[num_oldest_real_page][
  425.              element_num-starting_element_num[num_oldest_real_page]]);
  426.             vm_access[num_oldest_real_page]=vm_access_num;
  427.           }
  428.       return result;
  429.     };
  430.  
  431. template <class T>
  432. int varray<T>::map_expanded_memory(
  433.   int  physical_page,
  434.   long logical_page)
  435. //      Associate a physical page in the physical page frame with a logical page
  436. // of expanded memory.
  437.     {
  438.       union REGS input_reg;
  439.       union REGS output_reg;
  440.  
  441.       input_reg.h.ah=0x44;
  442.       input_reg.h.al=physical_page;
  443.       input_reg.x.bx=(unsigned int) logical_page;
  444.       input_reg.x.dx=expanded_memory_handle;
  445.       int86(0x67,&input_reg,&output_reg);
  446.       return (output_reg.h.ah == 0);
  447.     }
  448.  
  449. #endif
  450.